The present invention relates generally to error-correcting codes and more particularly to a single bit error correcting, double bit error detecting, pair error correcting code.
In data communication systems, it is often desirable and necessary to ensure the integrity of the data being transferred. To accomplish this, various error correction and detection circuits in code have been developed. Error correcting codes (ECCs) are used to maintain data integrity in the presence of unreliable hardware or noisy data transmission environments.
These codes fall into a number of xe2x80x9cdistancexe2x80x9d categories. The distances are measured in a higher dimensional space where a code is viewed as a packing of hyperspheres with the code word at the center of a sphere having a specified distance from the code word at the center of the next sphere. For example, a distance-4 code has the code word at the center of a sphere having a radius of 2 and no other code word closer than 4. These categories are:
A distance-2 code (also known as parity code) can detect any single bit error but cannot correct it. This is commonly used where errors are thought to be rare but cannot be tolerated.
A distance-3 code (also known as a single error correcting (SEC) or Hamming code) can correct any single bit error but will mis-correct double bit errors. This is not commonly used because of the xe2x80x9csilent data corruptionxe2x80x9d of double bit errors.
A distance-4 code (also known as a single error correcting, double error detecting (SEC-DED code) can correct any single bit error and detect any double bit error. This is the most commonly used error code today.
A distance-5 or a distance-6 code (also known as double error correcting (DEC) code) can correct double bit errors. This is not commonly done because the circuitry that is required for such codes is large, slow, expensive, and complex.
The ordinary distance-4 codes fail to correct for double bit errors. The distance-5 or greater codes can correct double bit errors but are realized in circuitry that is generally very complex relative to distance-4 codes.
Some codes (also known as pair error correcting (PEC) code) can correct errors in adjacent bit pairs by the overlap of two codes, but require many code bits for a given size of data word protected.
While random double bit errors are not common in most current applications, part failures are common enough to warrant a method of protecting the data from them. A code has long been sought which would more efficiently (1) correct all single bit errors; (2) correct specified pairs of double bit errors; and (3) detect all other double bit errors.
The present invention provides a cyclic SEC-DED-PEC code which has the characteristics of two different distance codes. The code of the present invention may be thought of in hyperspace as a hypersphere of a certain distance having spikes extending from the center of the hypersphere to the tip of the spike a further distance. This presents a xe2x80x9chyper-macexe2x80x9d, thus the name xe2x80x9cMace Codexe2x80x9d, having the property that it is a certain distance code generally and a further distance code in the direction of the spikes. The code further has the property that, if the description of the code is permutated by a cyclic permutation, the same code is obtained. To describe the Mace Code, the same notation as used in the George D. Zuras and Alexander J. Neudeck patent (U.S. Pat. No. 5,539,754) is used herein.
The present invention further provides circuitry for a code that is only slightly more complex than an ordinary distance-4 code but which can correct more of the errors that are likely to occur.
The present invention further provides a system that can correct single errors and adjacent pair errors, but requires far fewer code bits for a given size of data word protected than conventional PEC systems.